#pragma once

#include <vector>

namespace solution_074
{

class Solution
{
public:
    bool searchMatrixLinear(std::vector< std::vector<int> >& matrix, int target)
    {
        int row = 0;
        while (row < (int)matrix.size()) {
            if (matrix[row][0] > target)
                break;
            else
                ++row;
        }
        --row;

        if (row < 0)
            return false;

        int col = 0;
        while (col < (int)matrix.front().size()) {
            if (matrix[row][col] > target)
                break;
            else
                ++col;
        }
        --col;

        if (col < 0)
            return false;

        return (matrix[row][col] == target);
    }

    bool searchMatrix(std::vector< std::vector<int> >& matrix, int target)
    {
        auto row = search_row(matrix, target);
        auto col = binary_search(matrix[row], target);
        return (col >= 0);
    }

private:
    int search_row(const std::vector< std::vector<int> >& matrix, int target)
    {
        int row_i = 0;
        int row_j = matrix.size() - 1;
        while (row_i < row_j) {
            int mid = (row_i + row_j) / 2;
            if (matrix[mid][0] <= target && matrix[mid+1][0] > target) {
                return mid;
            } else {
                if (matrix[mid][0] > target)
                    row_j = mid;
                else if (matrix[mid][0] <= target)
                    row_i = mid + 1;
            }
        }
        return matrix.size() - 1;
    }

    int binary_search(std::vector<int>& vector, int target)
    {
        int i = 0;
        int j = (int)vector.size() - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (vector[mid] == target)
                return mid;
            else if (vector[mid] > target)
                j = mid - 1;
            else
                i = mid + 1;
        }
        return -1;
    }
};

}  /* namespace solution_074 */
